1. Field of the Invention
The present invention relates to the transmission of data packets in computer networks and in particular to the proper forwarding of such data packets the content of which may have been intentionally changed.
2. Prior Art
It is well known in computer networks for devices connected to the network to communicate with each other by sending data to each other in the form of data packets. The precise content of each packet will depend upon the communication protocol in operation but typically each data packet may contain a destination address identifying the intended recipient of the data packet, a source address identifying the sender of the packet, and the data itself Additionally, there may be protocol specific sections of the data packet, for instance in the Ethernet protocol each data packet typically contains a type identifier indicating for instance the type of packet which is being transmitted or the length of the data section of the packet. Finally, there is usually provided at the end of the data packet a sequence of bits enabling error detection to be carried out.
In particular, this sequence of bits, which is commonly known as a frame check sequence (FCS), is a sequence of bits generated by performing some mathematical algorithm or procedure on all of the bits forming the rest of the data packet. On receipt of the data packet, the receiving station can check for errors which may have occurred during transmission of the packet by performing the appropriate mathematical algorithm or procedure on the data packet as received and comparing this to the received FCS. If there is a difference in this comparison the received data packet is discarded as containing an error.
In computer networks the network devices are not connected directly to each other and the data packets which are sent as described above in fact travel via a number of communication hubs which function to receive and retransmit the packet to enable the packets to travel throughout the network. There are certain types of communications hub, such as bridges, switches and routers, which have a certain amount of intelligence such that the packets they receive are retransmitted only on the route or routes necessary to enable the received packet to reach its intended destination. To achieve this, such hubs have some memory to enable the data packet to be received into memory and held while the required analysis of the destination takes place before being retransmitted.
This temporary storage of the data packet enables the communications hub also to make modifications to the data packet if this is required. Such modifications may be made in circumstances where for instance the hub is at an interface between two network segments operating slightly different network protocols or supporting different network features. The modifications would generally not affect the data portion of the packet or probably the destination or source address of the packet. However, the type identifier mentioned above may be altered or additional sections may be inserted into the packet specific to the protocol via which the packet is to be transmitted. Equally, upon reaching the end of the particular network segment in question, the inserted data must be removed from the data packet or the data packet must be otherwise restored to its original condition. One particular circumstance in which data packets may be altered in this fashion is on being passed to a portion of a computer network which supports virtual LANs (VLANs) in which case it is necessary to insert a portion of data known as a VLAN tag into the data packet and to remove it when the packet leaves the portion of the network which supports this feature.
The present invention is not directly concerned with the reasons or mechanisms for altering the data packets in this way, although in the specific embodiment described later on a mechanism of inserting and removing a VLAN tag will be described. Rather, the present invention is related to the problems created in relation to the FCS when the packet is altered as outlined above.
It will be appreciated that whenever the overall content of the data packet changes the FCS at the end of the data packet must also be changed if it is to remain consistent with the content of the packet itself. However, in a circumstance where a packet is to be altered as outlined above it is also necessary to check the current FCS for correspondence with the existing data packet in order to detect any errors, before discarding the FCS and replacing it with the new one.
There have previously been proposed methods for dealing with the requirement to change the FCS when the content of the data packet changes but these have exhibited certain problems. For instance, it has been proposed simply to recalculate the FCS without checking the integrity of the received data and just transmitting the altered packet with a good FCS on the assumption that a packet containing an error would have been dropped before it reached the point at which the packet was altered. Such methods do not taken into account the possible corruption of a packet while it is being handled in the device performing the alteration to the packet. For instance, a good packet could be corrupted while being stored in the memory. A good FCS would then be appended to a bad packet and a receiving device would accept the packet and try to treat the corrupted data as valid data.
A second previously proposed method uses a multiplexer to control the flow of data to the transmission section of the communications hub and another data path to check the previous FCS. However, the generation in this scheme of two data paths raises the possibility that data corruption may occur on the transmit path which would not be detected on the checking path and this would result in the same difficulties as mentioned above. In this scheme, there is also a considerable delay introduced in the transmit path in the case that a section of the packet is being removed, for instance a VLAN tag. In this case, the FCS checker still needs to process the removed bits along with the original FCS before the transmission can be completed with the new FCS. Typically this introduces a requirement for 64 bits of delay into the transmission path, reflecting the sizes of the original FCS and VLAN tag being 32 bits.
A third general approach to the problem mentioned above is to use a mathematical algorithm to calculate the position of the change in the data in the packet and applying a corresponding offset to the existing FCS to correct it for the modified packet. This solution however requites complex mathematical calculation to be carried out on the asserted data and the existing packet and the additional results. This process involves calculating several FCSs using different parts of the packet along with various masks and is very gate intensive when implemented in hardware.
The present invention provides apparatus for the alteration and output of an input data packet in a computer network, the data packet comprising communication data, and check data, the check data bearing a predetermined relationship to the communication data whereby integrity of the data packet can be checked; the apparatus comprising:
means arranged to alter the communication data of an input data packet;
storage means arranged to store said data packet such that said communication data may be output from said storage means in either its un-altered or altered condition;
output means arranged to receive from said storage means said communication data in its altered condition, to determine new check data on the basis of said communication data in its altered condition, and to output said communication data in its altered condition and said new check data as an output data packet; and
checking means arranged to receive from said storage means said communication data in its unaltered condition and said check data of said input packet, to determine whether said received check data bears said predetermined relationship to said un-altered communication data, and to give an indication, if it does not, to said output means;
said output means being further arranged to corrupt said output data packet if said indication is received.
In this arrangement it is the same data, that is the data output from the storage means, which both forms the new data packet and is the basis for the data integrity check. The possibility for the data received by the output means and by the checking means to differ is very small and therefore the likelihood of corrupt data being output in an apparently un-corrupt output packet is largely reduced.
Preferably timing means controls the relative timing of the output of data from said storage means to said output means and to said checking means such that said indication, if given by said checking means, occurs prior to the completion of the determination of said new check data;
Also, in a preferred embodiment the storage means comprises a first memory device arranged to store said data packet in its un-altered condition, and a second memory device having a plurality of memory locations into which data is written cyclically such that the existing data is sequentially over-written by new data and from which data can be read from desired ones of said memory locations; and
further comprising control means arranged to control the operation of the storage means such that the data of the unaltered data packet stored in said first memory device together with any additional data introduced by said means arranged to alter the communication data is read sequentially into said second memory device, and to control the locations from which data is read out from said second memory device to said output means and to said checking means such that the communication data of the data packet is received in its altered condition by said output means and in its un-altered condition by said checking means.
In the preferred embodiment described later, the alteration which is made to the data packet is the insertion or removal of a predetermined portion of data (eg. VLAN tag) at a predetermined location in the communication data.
For the removal of such a data portion the invention provides apparatus for the alteration and output of an input data packet in a computer network, the data packet comprising communication data and check data, the check data bearing a predetermined relationship to the communication data whereby integrity of the data packet can be checked; the apparatus comprising:
storage means arranged to store said input data packet;
output means arranged to receive from said storage means said communication data of said input data packet with the exception of a predetermined portion of said communication data to form new communication data, of an output data packet, and to determine new check data on the basis of said new communication data to complete said output data packet; and
checking means arranged to receive from said storage means said communication data and check data of said input data packet, to determine whether said received check data bears said predetermined relationship to said communication data, and to give an indication, if it does not, to said output means;
said output means being further arranged to corrupt said output data packet if said indication is received.
For the insertion of such a data portion the invention provides apparatus for the alteration and output of an input data packet in a computer network, the data packet comprising communication data and check data, the check data bearing a predetermined relationship to the communication data whereby integrity of the data packet can be checked; the apparatus comprising:
storage means arranged to store said input data packet and a further data portion to be inserted into the communication data of said input data packet at a predetermined location;
output means arranged to receive from said storage means said communication data of said input data packet with said data portion inserted at said predetermined location to form new communication data of an output data packet, and to determine new check data on the basis of said new communication data to complete said output data packet; and
checking means arranged to receive from said storage means said communication data and check data of said input data packet, to determine whether said received check data bears said predetermined relationship to said communication data, and to give an indication, if it does not, to said output means;
said output means being further arranged to corrupt said output data packet if said indication is received.
In the preferred embodiment, the above two defied apparatus have a pair of read pointers controlling the output from the storage means, the relative positions of the read pointers being controller such that the data as defined above is read out to the output and checking means.
This invention therefore provides a simple but effective technique for the alteration of data packets as described.